package q543;

/**
 * 543. 二叉树的直径
 */
public class Solution {

    int mergetMax = 0;

    public int diameterOfBinaryTree(TreeNode root) {
        diameterOfBinaryTree2(root);
        return mergetMax;
    }


    public int diameterOfBinaryTree2(TreeNode root) {
        if (root == null) return -1;
        int left = diameterOfBinaryTree2(root.left);
        int right = diameterOfBinaryTree2(root.right);
        int merge = left  + right + 2;
        mergetMax = Math.max(merge, mergetMax);
        return Math.max(left, right) + 1;
    }

}


class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;

    TreeNode() {
    }

    TreeNode(int val) {
        this.val = val;
    }

    TreeNode(int val, TreeNode left, TreeNode right) {
        this.val = val;
        this.left = left;
        this.right = right;
    }
}
